这个帖子是图论算法的合集，你会看到：
· 图的存储
· 图的遍历
· 并查集
· 最小生成树
· 最短路
· 拓扑排序
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
图的存储
图的存储分为两种：邻接表和邻接矩阵
邻接矩阵存图：
邻接矩阵存图思想很简单：
对于无权图，如果 iii 和 jjj 有一条边相连，那么 graph[i][j]=1graph[i][j]=1graph[i][j]=1，否则 graph[i][j]=0graph[i][j]=0graph[i][j]=0
对于有权图，如果 iii 和 jjj 有一条权值为 kkk 的边相连，则 graph[i][j]=kgraph[i][j]=kgraph[i][j]=k，否则 graph[i][j]=∞graph[i][j]=\inftygraph[i][j]=∞
C++模板代码：
Python模板代码：
空间复杂度：O(V2)O(V^2)O(V2)
练习：
A358. 有向无权图1
A355. 有向带权图1
A352. 无向无权图1
邻接表存图：
我们会发现，邻接矩阵存图，对于稀疏图而言，浪费了太多空间在 000 或 ∞\infty∞ 上，这会导致当 nnn 越来越大，但是图是稀疏图的时候，会开不下邻接矩阵。因此，我们可以把邻接矩阵中所有的 000 或者 ∞\infty∞ 去掉，变成邻接表，adj[i]adj[i]adj[i] 变成一个（C++）向量或者（Python）列表动态添加边的信息。
C++模板：
Python模板代码：
空间复杂度：O(E)O(E)O(E)
练习：
A351. 有向带权图2
A650. 有向无权图2
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
图的遍历
图的遍历，主要分为深度优先遍历和广度优先遍历，内容和深度优先搜索（Depth−First−SearchDepth-First-SearchDepth−First−Search）与广度优先搜索（Breadth−First−SearchBreadth-First-SearchBreadth−First−Search）几乎一样。
深度优先遍历：
以邻接表为例，深度优先遍历就是不走回头路，一直往下遍历，遍历到没有未访问的结点就返回。
C++模板代码：
Python模板代码：
广度优先遍历：
依然以邻接表为例，广搜像水流一样要流经所有结点，虽然搜索时比深搜效率快很多，但是在这里和深搜遍历就效率上来谈没什么大的区别。
C++模板代码：
Python模板代码：
时间复杂度：都是 O(V)O(V)O(V)
练习：
A4762. 关系网络
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
并查集：
并查集（Union−FindUnion-FindUnion−Find）是一种用于管理不相交集合的高效数据结构，主要解决元素的分组、合并与连通性查询问题。主要分成查询（FindFindFind）和合并（UniteUniteUnite）两个操作。可以形象地想象成是认“义父”操作
C++模板代码：
Python模板代码：
单次查找函数的时间复杂度：O(logE)O(\log E)O(logE)
总时间复杂度：O(ElogE)O(E\log E)O(ElogE)
练习：
A567. 亲戚1
A565. 亲戚2
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
生成树：
在连通图 GGG 中，对于 ∀u、v∈G.V\forall u、v\in G.V∀u、v∈G.V，有且仅有一条路，且生成树中不存在回路。
最小生成树：
是所有的生成树中边权值和最小的一棵生成树。常见算法有 KruskalKruskalKruskal（克鲁斯卡尔）和 PrimPrimPrim（普里姆）
求最小生成树的方法：
· KRUSKAL 算法：
1、将所有的边按从小到大顺序排序
2、按排序顺序选择联通 u、vu、vu、v 两个结点的边
3、通过并查集判断 u、vu、vu、v 两个结点是否联通，如果不联通则合并两个结点
4、选到 n−1n-1n−1 条边的时候，根据树的定义可以直接返回
C++模板代码：
Python模板代码：
时间复杂度：O(ElogE)O(E\log E)O(ElogE)
空间复杂度：O(V+E)O(V+E)O(V+E)
· PRIM算法：
1、初始化距离数组为 ∞\infty∞，选择初始结点，将其距离设为 000
2、遍历所有结点中未标记的结点，选择其中距离最小的结点，进行标记
3、从该结点出发，遍历其能够到达的所有结点，更新其距离
4、重复执行操作 222 和 333 直到全部顶点都被标记
C++模板代码：
Python模板代码：
时间复杂度：O(V2)O(V^2)O(V2)
空间复杂度：O(V+E)O(V+E)O(V+E)
练习：
A555. 最小生成树
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
最短路算法：
即求从结点uuu到结点vvv所有的道路中边权值之和最短的一条道路的算法。分为单源最短路和多源最短路算法。单源最短路即从定结点uuu到所有其它结点vvv的算法，而多源最短路算法可以求∀u∈G.V\forall u \in G.V∀u∈G.V作为起点到其它结点vvv的最短路。
单源最短路算法：
常见的有 DijkstraDijkstraDijkstra（迪杰斯特拉）、Bellman−FordBellman-FordBellman−Ford（贝尔曼-福特）和 SPFASPFASPFA 三个算法。
求单源最短路的方法：
· DIJKSTRA
1、初始化距离数组为 ∞\infty∞，选择初始结点，将其距离设为 000
2、遍历所有结点中未标记的结点，选择其中距离最小的结点，进行标记
3、从该结点出发，遍历其能够到达的所有结点，更新其距离
4、重复执行操作 222 和 333 直到全部顶点都被标记
C++模板代码：
Python模板代码：
时间复杂度：O(V2)O(V^2)O(V2)
空间复杂度：O(V+E)O(V+E)O(V+E)
· DIJKSTRA 的优化
根据上面代码，用 O(V2)O(V^2)O(V2) 的时间复杂度取求最短路无疑是有点浪费时间的，时间都花在了找最小值上面。考虑利用 STLSTLSTL 容器的特性来优化 DijkstraDijkstraDijkstra，我们需要一个能够动态找最小值的容器。
因此，我们可以利用优先队列（堆）动态找到最小值来优化 DijkstraDijkstraDijkstra 算法：
C++模板代码：
Python模板代码：
时间复杂度：O(VlogV+ElogV)O(V\log V+E\log V)O(VlogV+ElogV)
DIJKSTRA 不适用的情况：
根据 DijkstraDijkstraDijkstra 算法的逻辑和流程，可以进行简单的模拟，易证它不适用于出现 负边权 的情况。
· BELLMAN-FORD：
1、遍历所有的边
2、从边的起点到终点做松弛操作
优化：如果没有进行过松弛操作则退出循环
C++模板代码：
Python模板代码：
· BELLMAN_FORD 变形——不超过 KKK 条边的最短路
对于某些题目，要求走的边数不超过 kkk 且求最短路，普通的 Bellman−FordBellman-FordBellman−Ford 算法肯定行不通。此时，我们可以使用 dpdpdp 思想，来进行最短路的计算，如下：
C++模板代码：
Python模板代码：
时间复杂度：O(VE)O(VE)O(VE)
空间复杂度：O(V+E)O(V+E)O(V+E)
· SPFA：
SPFASPFASPFA（Shortest Path Faster AlgorithmShortest\,\,Path\,\,Faster\,\,AlgorithmShortestPathFasterAlgorithm）是 Bellman−FordBellman-FordBellman−Ford 算法的进阶版本，通过队列来对其进行优化。
C++模板代码：
时间复杂度：O(kV)O(kV)O(kV)（kkk为常数，通常是在 [2,3][2,3][2,3] 之间）
空间复杂度：O(V+E)O(V+E)O(V+E)
队列空间复杂度：0<x≤O(V)0< x\leq O(V)0<x≤O(V)
练习：
A569. 单源最短路1
多源最短路算法：
一般用 Floyd−WarshallFloyd-WarshallFloyd−Warshall 算法（也有版本叫它 Floyed−WarshallFloyed-WarshallFloyed−Warshall）。
求多源最短路的方法：
· FLOYD-WARSHALL：
Floyd−WarshallFloyd-WarshallFloyd−Warshall算法可能是大多数人最喜欢的方法。其核心思想是动态规划，把每个结点作为中转点、起点和终点进行计算。注意不能够把它循环顺序反过来，否则结果会出问题。
C++模板代码：
Python模板代码：
时间复杂度：O(V3)O(V^3)O(V3)
空间复杂度：O(V2)O(V^2)O(V2)
拓扑排序
图的拓扑排序定义：
对于有向无环图（简称 DAGDAGDAG）是将 GGG 中所有顶点排成一个线性序列，使得 ∀u,v∈G.V\forall u,v\in G.V∀u,v∈G.V，若边 <u,v<u,v<u,v >>> ∈G.E\in G.E∈G.E，则 uuu 在线性序列中出现在 vvv之前。
1、选择一个入度为0的顶点并输出
2、从网中删除此顶点及所有出边
3、重复操作 111 和 222 直到没有符合要求的点
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
备注：
符号解释：
GGG：表示一张图
VVV：表示点的数量
EEE：表示边的数量
G.VG.VG.V：指点的集合
G.EG.EG.E：指边的集合
